#ifndef AUGMENTED_CONTOURTREE_H
#define AUGMENTED_CONTOURTREE_H

#include <QList>

#ifdef NO_HASHMAP
#include <map>
#else
#include <hash_map>
#endif

#include "arc.h"
#include "contourtree.h"
#include "interval_tree.h"
#include "contreeconstructor3d.h"

namespace PBVP {
	///	Augmented Contour Tree with Topology info 
	class AugmentedContourTree : public ContourTree {
	public:
		/**
		* Construct an Augmented Contour Tree from a contour tree
		*/
		AugmentedContourTree(ContourTree* conTree);

		/** 
		 * Construct an empty Augmented Contour Tree and then load it later 
		 * from a file.
		 */
		AugmentedContourTree();

		virtual ~AugmentedContourTree();

		/**
		* Write the contour tree to a file
		*/
		virtual bool saveFile(const char* fname);

		/**
		* Read contents of a contour tree from a file
		*/
		virtual bool loadFile(const char* fname);

		/**
		* Compute the BettiNumbers for the level set of isovalue x
		*/
		BettiNumber getBettiNumbers(float x);

		void calcBettiNumbers();

		/// Find the list of intersected arc when the contree is cut at x
		/** 
		 *  
		 * @param pData
		 * @param x
		 * 
		 * @return std::vector<SuperArc>*
		 */
		std::vector<SuperArc>* cut(float x);

		friend class DualGraph;

	protected:

#ifdef NO_HASHMAP
		typedef std::map<int, SuperArc> SuperArcMap; 
#else
		typedef stdext::hash_map<int, SuperArc> SuperArcMap;
#endif
		///
		SuperArcMap *m_pArcs;
		///
		IntervalTree< SuperArc >* m_pIntvTree;

		/**
		 * Add topology info to contree edges
		 * @param conTree Input contour tree
		 */
		void augment(ContourTree* conTree);

		/**
		 * Remove redundant arcs and reduce the contour tree size 
		 */
		virtual void reduce();

		/**
		* Finalize the tree and construct search structures
		*/
		void finalize();

		/**
		 * Remove a node with given Id 
		 *  
		 * Only a node with degree 1 or 2 may be removed. Furthermore, 
		 * the two arcs connected to a degree 2 node must have same 
		 * topology in order for its removal. 
		 *  
		 * @param id The id of the node to be removed
		 */
		virtual void removeNode(int id);

		/**
		 * Add an arc between node v1 and v2 
		 *  
		 * @param v1
		 * @param v2
		 * @param xe
		 * @param be
		 * @param intra
		 * @param x1
		 * @param x2
		 */
		void addArc(int v1, int v2, int xe, int be, int intra = -1, int x1 = -1, int x2 = -1);

	};
}
#endif
